package com.simon.study.algorithm.review;

import java.util.Arrays;

/**
 * <p>
 *
 * @author simon
 */
public class AllSort {

    public static void main(String[] args) {
        int[] arr = {10, 2, 7, 4, 1, 8, 3, 6, 5, 9, 11};

        mergeSort(arr, 3, 7);
        System.out.println(Arrays.toString(arr));

        mergeSort(arr, 0, 15);
        System.out.println(Arrays.toString(arr));
    }

    public static void select(int[] arr, int as, int ae){
        if(as <  0 || as > ae){ return; }
        if(ae >= arr.length){ ae = arr.length-1; }

        for (int i = as; i < ae; i++) {
            for (int j = i+1; j <= ae; j++) {
                if( arr[i] > arr[j] ){ swap(arr, i, j); }
            }
        }
    }

    public static void bubble(int[] arr, int as, int ae){
        if(as <  0 || as > ae){ return; }
        if(ae >= arr.length){ ae = arr.length-1; }

        for (int i = as; i < ae; i++) {
            for (int j = as; j < ae; j++) {
                if(arr[j] > arr[j+1]){ swap(arr, j, j+1); }
            }
        }
    }

    public static void insert(int[] arr, int as, int ae){
        if(as <  0 || as > ae){ return; }
        if(ae >= arr.length){ ae = arr.length-1; }

        for (int i = as+1; i <= ae; i++) {
            for (int j = i; j > as; j--) {
                if(arr[j] < arr[j-1]){ swap(arr, j, j-1); }
                else{
                    break;
                }
            }
        }
    }



    public static void mergeSort(int[] arr, int as, int ae){
        if(as <  0 || as > ae){ return; }
        if(ae >= arr.length){ ae = arr.length-1; }

        if(as >= ae){ return; }

        int mid = as + ((ae-as)/2);
        mergeSort(arr, as, mid);
        mergeSort(arr, mid+1, ae);
        merge(arr, as, ae, mid);
    }

    public static void merge(int[] arr, int as, int ae, int mid){
        int lp = as, mp = mid+1, di = 0;

        int[] dup = new int[ae - as + 1];
        while (lp<= mid && mp <= ae){
            dup[di++] = arr[lp] <= arr[mp] ? arr[lp++] : arr[mp++];
        }

        while (lp <= mid){ dup[di++] = arr[lp++]; }
        while (mp <= ae ){ dup[di++] = arr[mp++]; }

        for (int i = 0; i < dup.length; i++) { arr[as+i] = dup[i]; }
    }

    public static void quickSort(int[] arr, int as, int ae){

        int t = as + (int)(Math.random()* (ae-as));


    }


    public static void swap(int[] arr, int i, int j){
        if(i == j){ return; }

        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
